/*
 * Copyright (c) 2011 Seoul National University
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * Authors: Jung Ho Ahn  ( gajh@snu.ac.kr )
 *
 */

#include <cassert>
#include <iostream>
#include <pthread.h>
#include <map>
#include "Graph.h"

using namespace std;


extern pthread_mutex_t hashmaps_m;
extern pthread_mutex_t read_file_m;


Graph::Graph(KmerCoverageTable * table_)
:table(table_)
{
}


Graph::~Graph()
{
}


void Graph::findLikelyNeighbors()
{
  if (table->display_confusing_kmers)
  {
    table->ctgout << "kmers that have neighbors among which it is not obvious to choose one per direction:" << endl;
  }
  // currently, check the following two levels
  for (int i = 0; i < table->numHashmaps; i++)
  {
    list<KmerNode *>::iterator it;
    list<KmerNode *> & graph = table->graphs[i];

    for (it = graph.begin(); it != graph.end(); ++it)
    {
      KmerNode * currGraphNode = *it;
      bool displayNode = false;

      // check the forward direction
      if (currGraphNode->numNext == 1)
      {
        assert(currGraphNode->next_type != nt_I);
      }
      else if (currGraphNode->numNext > 1)
      {
        float bestScore = 0.0;
        float secondBestScore = 0.0;
        float currScore = 0.0;
        float totalScore = 0.0;

        for (int ii = 0; ii < 4; ii++)
        {
          int i = currGraphNode->isKmerRC ? (3 - ii) : ii;
          if (currGraphNode->next.nodes[i].node == NULL)
          {
            continue;
          }

          Node * nextNode = currGraphNode->next.nodes[i].node;
          if (nextNode->type == ndt_contig)
          {
            ContigNode * nContigNode = (ContigNode *) nextNode;

            if (nContigNode->length == table->getKmersize())
            {
              if (nContigNode->next == NULL)
              {
                currScore = nContigNode->hitcount;
              }
              else
              {
                currScore = nContigNode->hitcount + ((KmerNode *)nContigNode->next)->hitcount;
              }
            }
            else
            {
              /*if (nContigNode->next == NULL)
              {
                currScore = 2.0 * nContigNode->hitcount / (nContigNode->length - (table->getKmersize()-1));
              }
              else
              {
                currScore = 2 * (1.0 * nContigNode->hitcount + ((KmerNode *)nContigNode->next)->hitcount) / (nContigNode->length + 1 - (table->getKmersize()-1));
              }*/
              currScore = nContigNode->lm_hitcount + 
                1.0 * nContigNode->hitcount / (nContigNode->length - (table->getKmersize()-1));
            }
          }
          else
          {
            KmerNode * nGraphNode = (KmerNode *) nextNode;
            assert(nGraphNode->hasBranch() == true);
            currScore = nGraphNode->hitcount;

            float nScore = 0.0;

            for (int jj = 0; jj < 4; jj++)
            {
              int j = nGraphNode->isKmerRC ? (3 - jj) : jj;
              if (nGraphNode->next.nodes[j].node == NULL)
              {
                continue;
              }

              if (nGraphNode->next.nodes[j].node->type == ndt_contig)
              {
                ContigNode * nnContigNode = (ContigNode *) nGraphNode->next.nodes[j].node;
                nScore = maxDouble(nScore, nnContigNode->lm_hitcount);
              }
              else
              {
                KmerNode * nnGraphNode = (KmerNode *) nGraphNode->next.nodes[j].node;
                nScore = maxDouble(nScore, nnGraphNode->hitcount);
              }
            }
            currScore += nScore;
          }
          currGraphNode->next.nodes[i].hitcount = currScore;

          if (bestScore <= currScore)
          {
            secondBestScore = bestScore;
            bestScore = currScore;
            currGraphNode->next_type = (nucleotide_type) i;
          }
          totalScore += currScore;
        }

        //if (bestScore / totalScore < table->dominantNodeThreshold &&
        if (bestScore / (secondBestScore + bestScore) < table->dominantNodeThreshold &&
            currGraphNode->hitcount >= table->minimal_hitcount_for_confusing_kmer)
        {
          displayNode = true;
        }
      }

      // check the backward direction
      if (currGraphNode->numPrev == 1)
      {
        assert(currGraphNode->prev_type != nt_I);
      }
      else if (currGraphNode->numPrev >= 1)
      {
        float bestScore = 0.0;
        float secondBestScore = 0.0;
        float currScore = 0.0;
        float totalScore = 0.0;

        for (int ii = 0; ii < 4; ii++)
        {
          int i = currGraphNode->isKmerRC ? (3 - ii) : ii;
          if (currGraphNode->prev.nodes[i].node == NULL)
          {
            continue;
          }

          Node * prevNode = currGraphNode->prev.nodes[i].node;
          if (prevNode->type == ndt_contig)
          {
            ContigNode * pContigNode = (ContigNode *) prevNode;

            if (pContigNode->length == table->getKmersize())
            {
              if (pContigNode->prev == NULL)
              {
                currScore = pContigNode->hitcount;
              }
              else
              {
                currScore = pContigNode->hitcount + ((KmerNode *)pContigNode->prev)->hitcount;
              }
            }
            else
            {
              /*if (pContigNode->prev == NULL)
              {
                currScore = 2.0 * pContigNode->hitcount / (pContigNode->length - (table->getKmersize()-1));
              }
              else
              {
                currScore = 2 * (1.0 * pContigNode->hitcount + ((KmerNode *)pContigNode->prev)->hitcount) / (pContigNode->length + 1 - (table->getKmersize()-1));
              }*/
              currScore = pContigNode->rm_hitcount + 
                1.0 * pContigNode->hitcount / (pContigNode->length - (table->getKmersize()-1));
            }
          }
          else
          {
            KmerNode * pGraphNode = (KmerNode *) prevNode;
            currScore = pGraphNode->hitcount;

            float pScore = 0.0;

            for (int jj = 0; jj < 4; jj++)
            {
              int j = pGraphNode->isKmerRC ? (3 - jj) : jj;
              if (pGraphNode->prev.nodes[j].node == NULL)
              {
                continue;
              }

              if (pGraphNode->prev.nodes[j].node->type == ndt_contig)
              {
                ContigNode * ppContigNode = (ContigNode *) pGraphNode->prev.nodes[j].node;
                pScore = maxDouble(pScore, ppContigNode->rm_hitcount);
              }
              else
              {
                KmerNode * ppGraphNode = (KmerNode *) pGraphNode->prev.nodes[j].node;
                pScore = maxDouble(pScore, ppGraphNode->hitcount);
              }
            }
            currScore += pScore;
          }
          currGraphNode->prev.nodes[i].hitcount = currScore;

          if (bestScore <= currScore)
          {
            secondBestScore = bestScore;
            bestScore = currScore;
            currGraphNode->prev_type = (nucleotide_type) i;
          }
          totalScore += currScore;
        }

        if (bestScore / (secondBestScore + bestScore) < table->dominantNodeThreshold &&
            currGraphNode->hitcount >= table->minimal_hitcount_for_confusing_kmer)
        {
          displayNode = true;
        }
      }

      if (displayNode == true)
      {
        if (table->display_confusing_kmers == true)
        {
          table->ctgout << *currGraphNode << endl;
        }
        
        if (table->disconnect_confusing_kmers == true)
        {
          // there are confusing branches -- disconnect them!

          //
          for (int ii = 0; ii < 4 && currGraphNode->isKmerRC == true; ii++)
          {
            currGraphNode->next_type = nt_I;
            int i = 3 - ii;
            if (currGraphNode->next.nodes[i].node == NULL)
            {
              continue;
            }

            Node * nextNode = currGraphNode->next.nodes[i].node;
            if (nextNode->type == ndt_contig)
            {
              ContigNode * nContigNode = (ContigNode *) nextNode;
              nContigNode->prev = NULL;
              //table->printAndUpdateContigSizeHistogram(nContigNode, 0, nContigNode->isKmerRC);
            }
          }
          for (int ii = 0; ii < 4 && currGraphNode->isKmerRC == false; ii++)
          {
            currGraphNode->prev_type = nt_I;
            int i = ii;
            if (currGraphNode->prev.nodes[i].node == NULL)
            {
              continue;
            }

            Node * prevNode = currGraphNode->prev.nodes[i].node;
            if (prevNode->type == ndt_contig)
            {
              ContigNode * pContigNode = (ContigNode *) prevNode;
              pContigNode->next = NULL;
              table->printAndUpdateContigSizeHistogram(pContigNode, 0, true);
            }
          }
        }
      }
    }
  }
}


void Graph::resolveConflicts()
{
  for (int i = 0; i < table->numHashmaps; i++)
  {
    list<KmerNode *>::iterator it;
    list<KmerNode *> & graph = table->graphs[i];

    for (it = graph.begin(); it != graph.end(); ++it)
    {
      KmerNode * currGraphNode = *it;

      while (currGraphNode->numPrev >= 1 &&
             currGraphNode->prev_type != nt_I &&
             currGraphNode->prev.nodes[currGraphNode->prev_type].node->type == ndt_kmer)
      {
        KmerNode * prevGraphNode = (KmerNode *)currGraphNode->prev.nodes[currGraphNode->prev_type].node;
        assert(prevGraphNode != NULL);
        if ((Node *)currGraphNode != prevGraphNode->next.nodes[prevGraphNode->next_type].node)
        {
          // there is a conflict. resolve!
          currGraphNode->prev.nodes[currGraphNode->prev_type].hitcount = 0.0;

          int idx = (currGraphNode->isKmerRC == true) ? 
            Kmer::ComplementaryNucleotide(currGraphNode->kmer->getMSBNucleotide()) :
            currGraphNode->kmer->getLSBNucleotide();
          if (prevGraphNode->next.nodes[idx].node != NULL)
          {
            assert(prevGraphNode->next.nodes[idx].node == currGraphNode);
            prevGraphNode->next.nodes[idx].hitcount = 0.0;
            //assert(prevGraphNode->numNext > 1);
          }

          currGraphNode->prev_type = nt_I;
          float bestScore = 0.0;
          for (int ii = 0; ii < 4; ii++)
          {
            int i = currGraphNode->isKmerRC ? (3 - ii) : ii;
            if (currGraphNode->prev.nodes[i].node != NULL &&
                currGraphNode->prev.nodes[i].hitcount > bestScore)
            {
              bestScore = currGraphNode->prev.nodes[i].hitcount;
              currGraphNode->prev_type = (nucleotide_type) i;
            }
          }
        }
        else
        {
          break;
        }
      }

      while (currGraphNode->numNext >= 1 &&
             currGraphNode->next_type != nt_I &&
             currGraphNode->next.nodes[currGraphNode->next_type].node->type == ndt_kmer)
      {
        KmerNode * nextGraphNode = (KmerNode *)currGraphNode->next.nodes[currGraphNode->next_type].node;
        assert(nextGraphNode != NULL);
        if ((Node *)currGraphNode != nextGraphNode->prev.nodes[nextGraphNode->prev_type].node)
        {
          // there is a conflict. resolve!
          currGraphNode->next.nodes[currGraphNode->next_type].hitcount = 0.0;
          int idx = (currGraphNode->isKmerRC == true) ? 
                    Kmer::ComplementaryNucleotide(currGraphNode->kmer->getLSBNucleotide()) :
                    currGraphNode->kmer->getMSBNucleotide();
          if (nextGraphNode->prev.nodes[idx].node != NULL)
          {
            nextGraphNode->prev.nodes[idx].hitcount = 0.0;
            //assert(nextGraphNode->numPrev > 1);
          }

          currGraphNode->next_type = nt_I;
          float bestScore = 0.0;
          for (int ii = 0; ii < 4; ii++)
          {
            int i = currGraphNode->isKmerRC ? (3 - ii) : ii;
            if (currGraphNode->next.nodes[i].node != NULL &&
                currGraphNode->next.nodes[i].hitcount > bestScore)
            {
              bestScore = currGraphNode->next.nodes[i].hitcount;
              currGraphNode->next_type = (nucleotide_type) i;
            }
          }
        }
        else
        {
          break;
        }
      }
    }
  }
}


void Graph::extractContig()
{
  for (int i = 0; i < table->numHashmaps; i++)
  {
    list<KmerNode *>::iterator it;
    list<KmerNode *> & graph = table->graphs[i];

    for (it = graph.begin(); it != graph.end(); ++it)
    {
      KmerNode * startNode = *it;
      /*if (table->display_fasta == true && startNode->isKmerRC == false)
      {
        ++it;
        KmerNode * startNodeRC = *it;

        if (startNode->valid == false || startNodeRC->valid == false)
        {
          continue;
        }
      }*/
      if (startNode->valid == false)
      {
        continue;
      }
      Node * currNode  = startNode;
      Node * prevNode  = NULL;

      set<Node *> currSet;
      uint64_t pointer = table->blockAllocators[0]->allocate(sizeof(ContigNode));
      ContigNode * currContigNode = new(pointer) ContigNode(table->ccount++);

      // forward (next) direction
      while (true)
      {
        assert(currNode != NULL);
        if (currSet.find(currNode) != currSet.end())
        {
          currContigNode->nrepeat = true;
          break;
        }
        if (currNode->type == ndt_contig)
        {
          // contigNode
          ContigNode * contigNode  = (ContigNode *) currNode;
          if (contigNode->valid == false)
          {
            break;
          }

          currContigNode->nucleotides += contigNode->isKmerRC ?
            Kmer::nucleotideToChar(Kmer::ComplementaryNucleotide(contigNode->kmer->getMSBNucleotide())) :
            Kmer::nucleotideToChar(contigNode->kmer->getLSBNucleotide());
          currContigNode->nucleotides += contigNode->nucleotides;
          currContigNode->length      += contigNode->length - (table->getKmersize() - 1);

          if (contigNode->next == NULL)
          {
            break;
          }
          else
          {
            KmerNode * nextNode = (KmerNode *) contigNode->next;
            if (nextNode->prev_type == nt_I || nextNode->prev.nodes[nextNode->prev_type].node != contigNode)
            {
              break;
            }
          }
          prevNode = currNode;
          currNode = contigNode->next;
          contigNode->next  = NULL;  // disconnect
          contigNode->valid = false;
          //table->activeContigs.erase(contigNode);
        }
        else
        {
          // graphNode
          KmerNode * graphNode = (KmerNode *) currNode;

          if (graphNode->valid == false)
          {
            break;
          }

          if (currContigNode->kmer == NULL)
          {
            currContigNode->kmer     = graphNode->kmer;
            currContigNode->isKmerRC = graphNode->isKmerRC;
            currContigNode->length   = table->getKmersize();
          }
          else
          {
            currContigNode->nucleotides += graphNode->isKmerRC ?
              Kmer::nucleotideToChar(Kmer::ComplementaryNucleotide(graphNode->kmer->getMSBNucleotide())) :
              Kmer::nucleotideToChar(graphNode->kmer->getLSBNucleotide());
            currContigNode->length ++;
            graphNode->valid = false;

            // disconnect graphNode->prev.nodes except prevNode
            assert(prevNode != NULL);

            if (graphNode->numPrev > 1)
            {
              for (int ii = 0; ii < 4; ii++)
              {
                int i = graphNode->isKmerRC ? (3 - ii) : ii;
                if (graphNode->prev.nodes[i].node == NULL || graphNode->prev.nodes[i].node == prevNode)
                {
                  continue;
                }

                if (graphNode->prev.nodes[i].node->type == ndt_contig)
                {
                  // contigNode
                  ContigNode * cNode = (ContigNode *) graphNode->prev.nodes[i].node;

                  if (cNode->valid == false)
                  {
                    continue;
                  }

                  cNode->next = NULL;

                  if (cNode->prev == NULL)
                  {
                    cNode->valid = false;
                    // move this from active to standalone
                    //table->activeContigs.erase(cNode);
                    table->standaloneContigs[0].insert(cNode);
                    if (table->minValidContigLength <= cNode->length)
                    {
                      table->ctgout << *cNode << endl;
                      if (table->display_fasta == true && startNode->isKmerRC == false)
                      {
                        cNode->fastaDisplay(table->fastaout);
                      }

                      if (table->createContigSizeHistogram == true && startNode->isKmerRC == false)
                      {
                        updateContigHistogram(cNode->getLength());
                      }
                    }
                  }
                }
              }
            }

          }

          if (graphNode->numNext == 0 || graphNode->next_type == nt_I)
          {
            break;
          }
          if (graphNode->numNext == 1)
          {
            prevNode = currNode;
            currNode = graphNode->next.nodes[graphNode->next_type].node;
          }
          else
          {
            int nextIdx = graphNode->next_type;
            assert(graphNode->next_type != nt_I);
            assert(graphNode->next.nodes[nextIdx].node != NULL);

            // disconnect others
            for (int ii = 0; ii < 4; ii++)
            {
              int i = graphNode->isKmerRC ? (3 - ii) : ii;
              if (i == nextIdx || graphNode->next.nodes[i].node == NULL)
              {
                continue;
              }

              if (graphNode->next.nodes[i].node->type == ndt_contig)
              {
                // contigNode
                ContigNode * cNode = (ContigNode *) graphNode->next.nodes[i].node;

                if (cNode->valid == false)
                {
                  continue;
                }

                cNode->prev = NULL;

                if (cNode->next == NULL)
                {
                  cNode->valid = false;
                  // move this from active to standalone
                  //table->activeContigs.erase(cNode);
                  table->standaloneContigs[0].insert(cNode);
                  if (table->minValidContigLength <= cNode->length)
                  {
                    table->ctgout << *cNode << endl;
                    if (table->display_fasta == true && startNode->isKmerRC == false)
                    {
                      cNode->fastaDisplay(table->fastaout);
                    }

                    if (table->createContigSizeHistogram == true && startNode->isKmerRC == false)
                    {
                      updateContigHistogram(cNode->getLength());
                    }
                  }
                }
              }
            }

            prevNode = currNode;
            currNode = graphNode->next.nodes[nextIdx].node;
            assert(currNode != NULL);
          }
        }
      }

      // backward (prev) direction
      currNode   = startNode;
      Node * nextNode  = NULL;

      while (true)
      {
        assert(currNode != NULL);
        if (currSet.find(currNode) != currSet.end())
        {
          currContigNode->prepeat = true;
          break;
        }
        if (currNode->type == ndt_contig)
        {
          // contigNode
          ContigNode * contigNode = (ContigNode *) currNode;
          if (contigNode->valid == false)
          {
            break;
          }
          currContigNode->length += contigNode->length - (table->getKmersize() - 1);
          if (currContigNode->kmer != NULL)
          {
            currContigNode->nucleotides = (currContigNode->isKmerRC ?
                Kmer::nucleotideToChar(Kmer::ComplementaryNucleotide(currContigNode->kmer->getMSBNucleotide())) :
                Kmer::nucleotideToChar(currContigNode->kmer->getLSBNucleotide())) + currContigNode->nucleotides;
          }
          currContigNode->nucleotides = contigNode->nucleotides + currContigNode->nucleotides;
          currContigNode->kmer        = contigNode->kmer;
          currContigNode->isKmerRC    = contigNode->isKmerRC;

          if (contigNode->prev == NULL)
          {
            break;
          }
          else
          {
            KmerNode * prevNode = (KmerNode *) contigNode->prev;
            if (prevNode->next_type == nt_I || prevNode->next.nodes[prevNode->next_type].node != contigNode)
            {
              break;
            }
          }
          nextNode = currNode;
          currNode = contigNode->prev;
          contigNode->prev  = NULL;  // disconnect
          contigNode->valid = false;
          //table->activeContigs.erase(contigNode);
        }
        else
        {
          // graphNode
          KmerNode * graphNode = (KmerNode *) currNode;
          if (graphNode->valid == false)
          {
            break;
          }

          graphNode->valid = false;

          if (currNode != startNode)
          {
            if (currContigNode->kmer != NULL)
            {
              currContigNode->nucleotides = (currContigNode->isKmerRC ?
                  Kmer::nucleotideToChar(Kmer::ComplementaryNucleotide(currContigNode->kmer->getMSBNucleotide())) :
                  Kmer::nucleotideToChar(currContigNode->kmer->getLSBNucleotide())) + currContigNode->nucleotides;
            }
            currContigNode->kmer = graphNode->kmer;
            currContigNode->isKmerRC = graphNode->isKmerRC;
            currContigNode->length ++;

            // disconnect graphNode->next.nodes except nextNode
            assert(nextNode != NULL);
            if (graphNode->numNext > 1)
            {
              for (int ii = 0; ii < 4; ii++)
              {
                int i = graphNode->isKmerRC ? (3 - ii) : ii;
                if (graphNode->next.nodes[i].node == NULL || graphNode->next.nodes[i].node == nextNode)
                {
                  continue;
                }

                if (graphNode->next.nodes[i].node->type == ndt_contig)
                {
                  // contigNode
                  ContigNode * cNode = (ContigNode *) graphNode->next.nodes[i].node;

                  if (cNode->valid == false)
                  {
                    continue;
                  }

                  cNode->prev = NULL;

                  if (cNode->next == NULL)
                  {
                    cNode->valid = false;
                    // move this from active to standalone
                    //table->activeContigs.erase(cNode);
                    table->standaloneContigs[0].insert(cNode);
                    if (table->minValidContigLength <= cNode->length)
                    {
                      table->ctgout << *cNode << endl;
                      if (table->display_fasta == true && startNode->isKmerRC == false)
                      {
                        cNode->fastaDisplay(table->fastaout);
                      }

                      if (table->createContigSizeHistogram == true && startNode->isKmerRC == false)
                      {
                        updateContigHistogram(cNode->getLength());
                      }
                    }
                  }
                }
              }
            }
          }

          if (graphNode->numPrev == 0 || graphNode->prev_type == nt_I)
          {
            break;
          }
          else if (graphNode->numPrev == 1)
          {
            nextNode = currNode;
            currNode = graphNode->prev.nodes[graphNode->prev_type].node;
          }
          else
          {
            int prevIdx = graphNode->prev_type;
            assert(graphNode->prev_type != nt_I);
            assert(graphNode->prev.nodes[prevIdx].node != NULL);

            // disconnect others
            for (int ii = 0; ii < 4; ii++)
            {
              int i = graphNode->isKmerRC ? (3 - ii) : ii;
              if (i == prevIdx || graphNode->prev.nodes[i].node == NULL)
              {
                continue;
              }

              if (graphNode->prev.nodes[i].node->type == ndt_contig)
              {
                // contigNode
                ContigNode * cNode = (ContigNode *) graphNode->prev.nodes[i].node;

                if (cNode->valid == false)
                {
                  continue;
                }

                cNode->next = NULL;

                if (cNode->prev == NULL)
                {
                  cNode->valid = false;
                  // move this from active to standalone
                  //table->activeContigs.erase(cNode);
                  table->standaloneContigs[0].insert(cNode);
                  if (table->minValidContigLength <= cNode->length)
                  {
                    table->ctgout << *cNode << endl;
                    if (table->display_fasta == true && startNode->isKmerRC == false)
                    {
                      cNode->fastaDisplay(table->fastaout);
                    }

                    if (table->createContigSizeHistogram == true && startNode->isKmerRC == false)
                    {
                      updateContigHistogram(cNode->getLength());
                    }
                  }
                }
              }
            }

            nextNode = currNode;
            currNode = graphNode->prev.nodes[prevIdx].node;
            assert(currNode != NULL);
          }
        }
      }

      startNode->valid = false;

      if (table->minValidContigLength <= currContigNode->length)
      {
        table->ctgout << *currContigNode << endl;
        if (table->display_fasta == true && startNode->isKmerRC == false)
        {
          KmerHash & hashmap = table->hashmaps[startNode->getKmer()->getLSW() % table->numHashmaps];
          KmerHash::const_iterator it = hashmap.find(startNode->getKmer());
          bool isPalindrome = (it->second.nodes->valid == false &&
              (it->second.nodes + 1)->valid == false);

          currContigNode->fastaDisplay(table->fastaout, isPalindrome);
        }

        if (table->createContigSizeHistogram == true && startNode->isKmerRC == false)
        {
          updateContigHistogram(currContigNode->getLength());
        }
      }
      table->standaloneContigs[0].insert(currContigNode);
    }
  }
}


void Graph::displayNodes()
{
  table->ctgout << "graphs" << endl;

  for (int i = 0; i < table->numHashmaps; i++)
  {
    list<KmerNode *>::iterator it;
    list<KmerNode *> & graph = table->graphs[i];

    for (it = graph.begin(); it != graph.end(); ++it)
    {
      KmerNode * currGraphNode = *it;
      table->ctgout << *currGraphNode << endl;

      if (currGraphNode->prev_type != nt_I)
      {
        if (currGraphNode->prev.nodes[currGraphNode->prev_type].node->type == ndt_kmer)
        {
          KmerNode * prevGraphNode = (KmerNode *)currGraphNode->prev.nodes[currGraphNode->prev_type].node;
          assert(prevGraphNode->next_type != nt_I);
          if ((Node *)currGraphNode != prevGraphNode->next.nodes[prevGraphNode->next_type].node)
          {
            table->ctgout << "prevNode match failed!" << endl;
          }
        }
      }
      if (currGraphNode->next_type != nt_I)
      {
        if (currGraphNode->next.nodes[currGraphNode->next_type].node->type == ndt_kmer)
        {
          KmerNode * nextGraphNode = (KmerNode *)currGraphNode->next.nodes[currGraphNode->next_type].node;
          assert(nextGraphNode->prev_type != nt_I);
          if ((Node *)currGraphNode != nextGraphNode->prev.nodes[nextGraphNode->prev_type].node)
          {
            table->ctgout << "nextNode match failed!" << endl;
          }
        }
      }
    }
  }
  table->ctgout << endl;
}

void Graph::updateContigHistogram(uint32_t length)
{
  if (table->contigSizeHistogram.find(length) == table->contigSizeHistogram.end())
  {
    table->contigSizeHistogram[length] = 1;
  }
  else
  {
    table->contigSizeHistogram[length]++;
  }
}

